/**打家劫舍
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * 计算从给定数组中抢劫房屋所能获得的最大金额。
 * 规则是不能同时抢劫相邻的房屋。
 * @param {number[]} nums - 每个房屋中存放的金额数组。
 * @return {number} - 所能抢劫到的最大金额。
 */
function rob(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  if (n === 1) return nums[0];
  const dp = new Array(n);
  // nums:1 0 3 5
  // dp:  1 1 4 6
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
  }
  return dp[n - 1];
}

/**
 * 数组中最长连续序列
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 * 输入：nums = [100,4,200,1,3,2]
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * @param {number[]} nums - 输入的数字序列
 * @returns {number} 最长递增子序列的长度
 */
var longestConsecutive = function (nums) {
  if (nums.length <= 1) return nums.length;
  const n = nums.sort((a, b) => a - b);
  //[0,1,1,2] [1,2,3,4,100,200]
  let maxlength = 1,
    cur = 1;
  for (let i = 1; i < n.length; i++) {
    if (n[i] === n[i - 1]) continue;
    if (n[i] - n[i - 1] === 1) {
      cur++;
    } else {
      cur = 1;
    }
    maxlength = Math.max(cur, maxlength);
  }
  return maxlength;
};
/**最长递增子序列（不一定连续） LIS-动态规划
 * 在一个数值序列中找到一个元素依次递增的子序列，且该子序列长度最大。
 * 计算给定数组中最长递增子序列的长度。
 * @param {number[]} nums - 输入的整数数组。
 * @return {number} - 最长递增子序列的长度。
 */
function lengthOfLIS(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  // 初始化 dp 数组，每个元素初始值为 1
  const dp = new Array(n).fill(1);
  // 5 3 6 7
  // 1 1 2 3  i：3 j：0
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  // 找出 dp 数组中的最大值
  let maxLength = 0;
  for (let i = 0; i < n; i++) {
    maxLength = Math.max(maxLength, dp[i]);
  }
  return maxLength;
}

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(' nums:', nums);
/**最长递增子序列LIS-贪心+二分
 * 计算给定数组中最长递增子序列的长度。
 * @param {number[]} nums - 输入的整数数组。
 * @return {number} - 最长递增子序列的长度。
 */
function lengthOfLIS2(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  const tails = [];
  for (const num of nums) {
    let left = 0,
      right = tails.length;
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (tails[mid] < num) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    if (left === tails.length) {
      tails.push(num);
    } else {
      tails[left] = num;
    }
  }

  return tails.length;
}
const nums2 = [10, 9, 2, 5, 3, 7, 101, 18];

/**
 * 二分查找算法
 * 在有序数组中查找特定元素的索引如果元素存在，则返回其索引；如果元素不存在，则返回-1
 *
 * @param {Array} arr - 有序数组
 * @param {*} target - 要查找的目标元素
 * @returns {number} - 目标元素的索引或-1（如果未找到）
 */
function binarySearch(arr, target) {
  // 初始化左右指针
  let left = 0,
    right = arr.length - 1;
  // 当左指针不大于右指针时，执行查找
  while (left <= right) {
    // 计算中间位置索引
    const mid = Math.floor((left + right) / 2);
    // 如果中间元素等于目标元素，返回中间元素的索引
    if (arr[mid] === target) return mid;
    // 根据中间元素与目标元素的比较结果，调整搜索范围
    arr[mid] < target ? (left = mid + 1) : (right = mid - 1);
  }
  // 如果未找到目标元素，返回-1
  return -1;
}
// 使用示例
const sortedArray = [1, 3, 5, 7, 9];
console.log(binarySearch(sortedArray, 5)); // 输出: 2（索引位置）
